package sort;

import java.util.Deque;
import java.util.LinkedList;

public class Sort {
    //非递归实现快速排序
    public void quickSort(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array, left, right);
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right - 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.poll();
            left = stack.poll();
            pivot = partition(array, left, right);
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }
    public int partition(int[] array, int left, int right) {
        int temp = array[left];
        while(left < right) {
            while(left < right && array[right] >= temp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= temp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = temp;
        return left;
    }
    //归并排序
    //时间复杂度 : O(n * logn)
    //空间复杂度 : O(N)
    //稳定性 : 稳定的
    public void mergeSort(int[] array) {
        mergeSortFunc(array,0,array.length - 1);
    }
    public void mergeSortFunc(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (right + left) / 2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,mid,right);
    }
    public void merge(int[] array, int start, int mid, int end) {
        int s1 = start;
        int s2 = mid + 1;
        int[] tmp = new int[end - start + 1];
        int k = 0;
        while(s1 <= mid && s2 <= end) {
            if (array[s2] < array[s1]) {
                tmp[k++] = array[s2++];
            } else {
                tmp[k++] = array[s1++];
            }
        }
        while(s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while(s2 <= end) {
            tmp[k++] = array[s2++];
        }

         for (int i = 0; i < tmp.length; i++) {
            array[start++] = tmp[i];
        }
    }
    //非递归实现归并排序
    public void mergeSort1(int[] array) {
        int gap = 1;
        while(gap < array.length) {
            for (int i = 0; i < array.length; i += gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                if (mid >= array.length) {
                    mid = array.length - 1;
                }
                int right = mid + gap;
                if (right >= array.length) {
                    right = array.length - 1;
                }
                merge(array,left,mid,right);
            }
            gap = gap * 2;
        }
    }
}
